// 力扣123. 买卖股票的最佳时机 III
public class Solution {
    public int maxProfit(int[] prices) {
        int buy1 = Integer.MIN_VALUE;
        int sell1 = 0;
        int buy2 = Integer.MIN_VALUE;
        int sell2 = 0;

        for (int price : prices) {
            buy1 = Math.max(buy1, -price);
            sell1 = Math.max(sell1, buy1 + price);
            buy2 = Math.max(buy2, sell1 - price);
            sell2 = Math.max(sell2, buy2 + price);
        }

        return sell2;
    }
}


// 力扣188. 买卖股票的最佳时机 IV
class Solution1 {
    public int maxProfit(int k, int[] prices) {
        int n = prices.length;
        if (n == 0 || k == 0) return 0;

        // 如果k很大，相当于无限次交易
        if (k >= n / 2) {
            int maxProfit = 0;
            for (int i = 1; i < n; i++) {
                if (prices[i] > prices[i - 1]) {
                    maxProfit += prices[i] - prices[i - 1];
                }
            }
            return maxProfit;
        }

        // dp[i][j][0] 表示第i天，完成了j次交易，不持有股票的最大利润
        // dp[i][j][1] 表示第i天，完成了j次交易，持有股票的最大利润
        int[][][] dp = new int[n][k + 1][2];

        // 初始化第一天的情况
        for (int j = 0; j <= k; j++) {
            dp[0][j][0] = 0;           // 第一天不买股票
            dp[0][j][1] = -prices[0];  // 第一天买入股票
        }

        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= k; j++) {
                // 当前不持有股票：要么昨天就不持有，要么昨天持有今天卖出（完成一次交易）
                dp[i][j][0] = Math.max(
                        dp[i - 1][j][0],
                        (j > 0) ? dp[i - 1][j - 1][1] + prices[i] : Integer.MIN_VALUE
                );

                // 当前持有股票：要么昨天就持有，要么昨天不持有今天买入
                dp[i][j][1] = Math.max(
                        dp[i - 1][j][1],
                        dp[i - 1][j][0] - prices[i]
                );
            }
        }

        // 找出所有交易次数中不持有股票的最大值
        int maxProfit = 0;
        for (int j = 0; j <= k; j++) {
            maxProfit = Math.max(maxProfit, dp[n - 1][j][0]);
        }
        return maxProfit;
    }
}